package day_2022_12_to_3.year2023;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2023/04/16 15:58
 **/
public class Day4_16_Num1157 {
    class MajorityChecker {
        int arr[];
        List<Integer> idx[];

        public MajorityChecker(int[] arr) {
            this.arr = arr;
            idx = new List[20005];
            for(int i = 1; i <= 20000; ++i) {
                idx[i] = new ArrayList<>();
            }
            for(int i = 0; i < arr.length; ++i) {
                idx[arr[i]].add(i);
            }
        }

        public int query(int left, int right, int threshold) {
            for(int i=0;i<30;i++){
                int a=arr[(int)(Math.random()*(right-left+1)+left)];
                int l1=0,l2=0,r1=idx[a].size()-1,r2=r1;
                //先找最左边
                while(l1<r1){
                    int mid=(l1+r1)>>1;
                    if(idx[a].get(mid)>=left){r1=mid;}
                    else{l1=mid+1;}
                    if(l1==r1-1){
                        if(idx[a].get(l1)>=left){r1=l1;}
                        break;
                    }
                }
                //寻找右边界：
                while(l2<r2){
                    int mid=(l2+r2)>>1;
                    if(idx[a].get(mid)<=right){l2=mid;}
                    else{r2=mid-1;}
                    if(l2==r2-1){
                        if(idx[a].get(r2)<=right){l2=r2;}
                        break;
                    }
                }
                if(l2-r1+1>=threshold){return a;}
                else if(r1-l1+1>=(right-left+1)*2){return -1;}
            }
            return -1;
        }
    }
}